package cn.orange.ch07_binarytree;

import cn.orange.TreeNode;

/**
 * LC700.二叉搜索树中的搜索
 */
public class LC700 {
    public TreeNode searchBSTD(TreeNode root, int val) { //迭代
        TreeNode curr = root;
        while (curr != null) {
            if (curr.val > val) {
                curr = curr.left;
            } else if (curr.val < val) {
                curr = curr.right;
            } else {
                break;
            }
        }
        return curr;
    }
    public TreeNode searchBST(TreeNode root, int val) { //递归
        if (root == null) return null;
        if (root.val > val) {
            return searchBST(root.left, val);
        }
        if (root.val < val) {
            return searchBST(root.right, val);
        }
        return root;
    }

    public static void main(String[] args) {
        LC700 alg = new LC700();
        TreeNode root = new TreeNode(4, new TreeNode(2), new TreeNode(7));
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        TreeNode treeNode = alg.searchBSTD(root, 2);
        System.out.println(treeNode);
    }
}
